#include <bits/stdc++.h>
#include "../../tools/tools.h"
using namespace std;


class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> ans;
        string str;
        str.resize(n);
        backTrace(ans, str, 0, n);
        return ans;
    }
    void backTrace(vector<string> & ans, string & str, int cur, int n) {
        if(cur == n) {
            string t = str;
            ans.push_back(t);
            return;
        }
        str[cur] = '1';
        backTrace(ans, str, cur + 1, n);
        if(cur == 0 || str[cur - 1] != '0') {
            str[cur] = '0';
            backTrace(ans, str, cur + 1, n);
        }
    }
};


int main(int argc, const char** argv) {
    // debug();
    return 0;
}
